package DataStructure;

/**
 * josephu 约瑟夫问题 约瑟夫环问题
 *
 * @time: 2021/3/27/027 17:15
 * @author: Zhurunhe
 */
public class CircleLinklistTest {
    public static void main(String[] args) {
        CircleLinklist circleLinklist = new CircleLinklist();
        circleLinklist.addChild(100);
        circleLinklist.show();
        circleLinklist.Outlist(100, 50, 99);

    }
}

class CircleLinklist {
    Child firstChild = null;

    public void addChild(int sum) {
        if (sum < 1) {
            System.out.println("输入的人数有误");
            return;
        }
        Child temp = null;
        for (int i = 1; i <= sum; i++) {
            Child child = new Child(i);
            if (i == 1) {
                firstChild = child;
                temp = firstChild;
                temp.next = firstChild;
            } else {
                temp.next = child;
                child.next = firstChild;
                temp = child;
            }
        }
    }

    public void show() {
        if (firstChild == null) {
            System.out.println("没有人参与");
            return;
        }
        Child temp = firstChild;
        while (true) {
            System.out.println(temp.toString());
            if (temp.next == firstChild) {
                break;
            }
            temp = temp.next;
        }
    }

    public void Outlist(int sum, int startone, int number) {
        if (startone < 0 || startone > sum || firstChild == null) {
            System.out.println("数据输入有误，请重新输入");
            return;
        }
        Child follow = firstChild;//
        while (true) {
            if (follow.next == firstChild) {
                break;
            }
            follow = follow.next;
        }
        for (int i = 1; i <= startone - 1; i++) {
            firstChild = firstChild.next;
            follow = follow.next;
        }

        while (true) {
            if (follow == firstChild) {
                break;
            }
            for (int i = 0; i < number - 1; i++) {
                firstChild = firstChild.next;
                follow = follow.next;
            }
            System.out.println(firstChild.id + "出列");
            firstChild = firstChild.next;
            follow.next = firstChild;


        }
        System.out.println(firstChild.id + "存活");


    }

}

class Child {
    int id;
    Child next;

    public Child(int id) {
        this.id = id;
    }

    @Override
    public String toString() {
        return "Child{" + "id=" + id + '}';
    }
}
